package 集合;

import java.util.HashMap;
import java.util.Map;

public class No219存在重复元素 {

    /**
     * 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，
     * 使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
     *
     * 示例 1:
     * 输入: nums = [1,2,3,1], k = 3
     * 输出: true
     * 示例 2:
     * 输入: nums = [1,0,1,1], k = 1
     * 输出: true
     * 示例 3:
     * 输入: nums = [1,2,3,1,2,3], k = 2
     * 输出: false
     *
     * 题目简单来说就是在[n-k,n]这个容量内,如果有两个元素相等,就返回true
     */

    public static boolean containsNearbyDuplicate(int[] nums, int k) {

        /**
         * 1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
         * 更新Map,将数据添加进入Map,自增?
         * 2、什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？
         * 当right-left=k时
         * 3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
         * 更新Map,自减left的value?
         * 4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
         * 按道理应该是在扩大时
         */
        int left=0;
        int right=0;
        /**
         * 仔细详细其实用Set就可以了,因为只要有相同的就返回true
         */
        Map<Integer,Integer> map=new HashMap<>();

        /**
         * right<nums.length这就是一个for循环...  与for循环是一模一样的,草率了
         */
        while(right<nums.length){
            if(map.containsKey(nums[right])&&map.get(nums[right])>0)
                return true;
            map.put(nums[right],map.getOrDefault(nums[right],0)+1);

            right++;
            if(right-left==k+1){
                map.put(nums[left],map.get(nums[left])-1);
                left++;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr1=new int[]{1,2,3,1};
        int[] arr2=new int[]{1,0,0,1};
        int[] arr3=new int[]{1,2,3,1,2,3};
        boolean flag = containsNearbyDuplicate(arr3, 2);
        System.out.println(flag);
    }

}
